package com.zhangx.datastructure.search;

import com.alibaba.fastjson.JSON;
import com.zhangx.datastructure.search.dto.BiNode;

/**
 * @ClassName BiTreeSearch
 * @Description 二叉查找树
 * @Author zhangx
 * @Date 2021/1/25 8:44
 **/
public class BiTreeSearch {

    public BiNode biTree;

    public BiNode searchNode;
    public BiNode parent;

    private void initTree(){
        BiNode a62 = new BiNode(62);
        BiNode b58 = new BiNode(58);
        BiNode b88 = new BiNode(88);
        BiNode c47 = new BiNode(47);
        BiNode c73 = new BiNode(73);
        BiNode c99 = new BiNode(99);
        BiNode d35 = new BiNode(35);
        BiNode d51 = new BiNode(51);
        BiNode d93 = new BiNode(93);
        BiNode e37 = new BiNode(37);

        a62.setLchild(b58);
        b58.setLchild(c47);
        c47.setLchild(d35);
        c47.setRchild(d51);
        d35.setRchild(e37);

        a62.setRchild(b88);
        b88.setLchild(c73);
        b88.setRchild(c99);
        c99.setLchild(d93);

        biTree = a62;
    }

    private boolean searchBST(int k,BiNode tree){
        int d = tree.getData();
        if (k < d){
            if (tree.getLchild()!=null){
//                记录要查找节点的父节点
                parent = tree.getLchild();
                searchBST(k,tree.getLchild());
            }
        }else if(k > d ){
            if (tree.getRchild()!=null){
                parent = tree.getRchild();
                searchBST(k,tree.getRchild());
            }
        }else {
            searchNode = tree;
            return true;
        }
        System.out.println("未找到");
        return false;
    }

    private boolean insertBST(int val){
        boolean flag = false;
        if (biTree == null){
            biTree = new BiNode(val);
            flag = true;
        }else {
            searchBST(val,biTree);
            if (null==searchNode){
//                只有查找不成功再插入
                BiNode s = new BiNode(val);
//                重点是在查询算法里面要记录下父节点
                if (parent==null){//代表真正的父实际是根节点，根节点是没有父的
                    if (val < biTree.getData()){
                        biTree.setLchild(s);
                        flag = true;
                    }else {
                        biTree.setRchild(s);
                        flag = true;
                    }
                }else {

                    if (val < parent.getData()){
                        parent.setLchild(s);
                        flag = true;
                    }else {
                        parent.setRchild(s);
                        flag = true;
                    }
                }
            }
        }

        return flag;
    }

    /**
     * 看P321，删除分三种情况
     * 1 叶子节点
     * 2 只有左或者右子树的节点
     * 3 左右都有子树--这个最复杂（要找到子树中最接近删除节点值的元素替换到删除节点，然后把接近节点干掉）
     * 二叉删除
     * @param t
     * @param k
     * @return
     */
    public boolean deleteBST(BiNode t,int k){
//        不停的递归，找到要删除的节点
        if (t == null){
            return false;
        }else {
            if (k == t.getData()){//找到就要删除
                return delete(t);
            }else if(k < t.getData()){
                return deleteBST(t.getLchild(),k);
            }else {
                return deleteBST(t.getRchild(),k);
            }
        }
    }

    /**
     * 从二叉树中删除节点p，重接左右子树
     * @param p
     * @return
     */
    private boolean delete(BiNode p) {
        BiNode q,s;
        if (p.getRchild()==null){//右子树为空只需重接左子树
            q = p;
            p = p.getLchild();
        }else if(p.getLchild() == null){//左子树为空只需重接右子树
            q = p;
            p = p.getRchild();
        }else {
//            左右都不为空-复杂
            q = p;
            s = p.getLchild();
            while (s.getRchild()!=null){//转左，然后向右走到尽头（找到待删除节点的前驱）
                q = s;
                s = s.getRchild();
            }
            p.setData(s.getData());//s指向被删除节点的直接前驱
            if (!q.equals(p)){
                q.setRchild(s.getLchild());//重接q的右子树
            }else {
                q.setLchild(s.getLchild());//重接q的左子树
            }

        }
        return true;
    }

    public static void main(String[] args) {
        BiTreeSearch biTreeSearch = new BiTreeSearch();
//        biTreeSearch.initTree();
//        biTreeSearch.searchBST(47,biTreeSearch.biTree);
//        if (biTreeSearch.searchNode!=null){
//            System.out.println(biTreeSearch.searchNode);
//            System.out.println(biTreeSearch.parent);
//        }
//        int[] arr = new int[]{62,88,58,47,35,73,51,99,37,93};
//        构造树的时候有讲究，要按照每一层来，这里构造了要删除的树
        int[] arr = new int[]{62,88,58,47,73,99,35,51,93,29,37,49,56,36,48,50};
        for (int i = 0; i < arr.length; i++) {
            biTreeSearch.insertBST(arr[i]);
        }
        System.out.println(JSON.toJSONString(biTreeSearch.biTree));
        biTreeSearch.deleteBST(biTreeSearch.biTree,47);
        System.out.println(JSON.toJSONString(biTreeSearch.biTree));
    }
}
